#include<vector>
#include<algorithm>

using namespace std;


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int index = 0;
        while (index < (int)(nums.size() - 3))
        {
            if ((long)nums[index] + nums[index + 1] + nums[index + 2] + nums[index + 3] > target) break;

            if ((long)nums[index] + nums[nums.size() - 3] + nums[nums.size() - 2] + nums[nums.size() - 1] < target) {
                index++;
                continue;
            }

            int index2 = index + 1;
            while (index2 < (int)(nums.size() - 2))
            {
                if ((long)nums[index] + nums[index2] + nums[index2 + 1] + nums[index2 + 2] > target) break;

                if ((long)nums[index] + nums[index2] + nums[nums.size() - 2] + nums[nums.size() - 1] < target) {
                    index2++;
                    continue;
                }

                long key = (long)target - nums[index] - nums[index2];
                int left = index2 + 1;
                int right = nums.size() - 1;
                while (left < right)
                {

                    long sum = (long)nums[left] + nums[right];
                    if (sum > key)
                    {
                        right--;
                    }
                    else if (sum < key)
                    {
                        left++;
                    }
                    else
                    {
                        vv.push_back({ nums[index],nums[index2],nums[left],nums[right] });
                        while (left < right && nums[left + 1] == nums[left])
                            left++;
                        while (left < right && nums[right - 1] == nums[right])
                            right--;
                        left++;
                        right--;
                    }
                }
                while (index2 < nums.size() - 2 && nums[index2 + 1] == nums[index2])
                    index2++;
                index2++;
            }
            while (index < nums.size() - 3 && nums[index + 1] == nums[index])
                index++;
            index++;
        }
        return vv;
    }
};

class Solution2 {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int index = 0;
        while (index < (int)(nums.size() - 3))
        {
            int index2 = index + 1;
            while (index2 < (int)(nums.size() - 2))
            {
                long key = ((long)target - nums[index]) - nums[index2];
                int left = index2 + 1;
                int right = nums.size() - 1;
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > key)
                    {
                        right--;
                    }
                    else if (sum < key)
                    {
                        left++;
                    }
                    else
                    {
                        vv.push_back({ nums[index],nums[index2],nums[left],nums[right] });
                        while (left < right)
                        {
                            if (nums[left + 1] == nums[left])
                                left++;
                            else
                                break;
                        }
                        while (left < right)
                        {
                            if (nums[right - 1] == nums[right])
                                right--;
                            else
                                break;
                        }
                        left++;
                        right--;
                    }
                }
                while (index2 < nums.size() - 2)
                {
                    if (nums[index2 + 1] == nums[index2])
                        index2++;
                    else
                        break;
                }
                index2++;
                left = index2 + 1;
                right = nums.size() - 1;
            }
            while (index < nums.size() - 3)
            {
                if (nums[index + 1] == nums[index])
                    index++;
                else
                    break;
            }
            index++;
        }
        return vv;
    }
};
int main()
{
    vector<int> v{1000000000,1000000000,1000000000,1000000000};
    Solution s;
    s.fourSum(v, -294967296);
    return 0;
}